// 删除有序数组中的重复项
// 思路：
// 1. 定义快慢指针，slow走在后面，fast走在前面探路
// 2. 找到一个不重复的元素就赋值给slow，注意先给slow++再赋值
// 这样就保证了nums[0, slow]都是无重复的

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        return slow + 1;
    }
};


// 删除排序数组中的重复元素
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;
            
        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        // 断开slow与后面的连接
        slow->next = nullptr;

        return head;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }

            fast++;
        }

        return slow;
    }
};


// 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 将nums中的0全部移除
        int p = removeElement(nums, 0);

        // 将[p, nums.size()-1]赋值为0即可
        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }

            fast++;
        }

        return slow;
    }
};


// 删除有序数组中的重复项
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针
        // slow走在后面，fast走在前面探路，遇到不相等的元素就赋值给slow，并且++
        // 注意赋值和++的先后顺序
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                slow++;
                nums[slow] = nums[fast];
            }

            fast++;
        }

        return slow + 1;
    }
};


// 删除排序链表中的重复项
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        slow->next = nullptr;

        return head;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }

            fast++;
        }

        return slow;
    }
};


// 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 将元素0全部移除
        int p = removeElement(nums, 0);

        // 将[p, nums.size()-1]全部置为0
        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 删除有序数组中的重复项
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast遇到不重复的数就赋值给slow，并且slow++
        // 要注意的是 赋值和++的先后顺序
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        return slow+1;
    }
};


// 删除排序链表的重复元素
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }

        // 断开与后面重复元素的连接
        slow->next = nullptr;

        return head;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast遇到值不为val的元素就赋值给slow，并且slow++
        // 需要注意赋值和slow++的先后顺序
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 移除零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 根据 移除元素 思路，将0全部移除
        int p = removeElement(nums, 0);

        // [p, nums.size-1]全部置0即可
        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 删除有序数组中的重复项
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针, slow走在后面，fast走在前面探路
        // fast找到一个不重复的元素就赋值给slow，并且slow++
        // 注意赋值和slow++的先后顺序
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != nums[slow])
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        return slow + 1;
    }
};


// 删除排序链表中的重复元素
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast遇到不重复的元素就让slow指向fast，然后slow走一步
        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(fast->val != slow->val)
            {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }

        // slow需要断开与后面重复元素的连接
        slow->next = nullptr;

        return head;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast遇到不为val的元素就赋值给slow，并且slow++
        // 还是需要注意slow++和赋值的先后顺序
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 移动零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 根据 移除元素 思路，将0全部移除
        int p = removeElement(nums, 0);

        // 将[p, nums.size()-1]全部赋值为0
        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    // 移除元素
    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 两数之和 - 输入有序数组
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            if(numbers[left] + numbers[right] == target)
            {
                return {left + 1, right + 1};
            }
            else if(numbers[left] + numbers[right] < target)
            {
                left++;
            }
            else if(numbers[left] + numbers[right] > target)
            {
                right--;
            }
        }

        return {-1, -1};
    }
};


// 删除有序数组中的重复项
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // 当fast找到不重复的元素就赋值给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != nums[slow])
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        return slow + 1;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // 当fast遇到值不为val的元素就赋值给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 移除零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 根据 移除元素 思路， 先将0全部移除
        int p = removeElement(nums, 0);

        // [p, nums.size()-1]全部置为0
        for(int i = p; i < nums.size(); i++)
            nums[i] = 0;
    }

    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 最长回文子串
class Solution {
public:
    string longestPalindrome(string s) 
    {
        string ret = "";

        for(int i = 0; i < s.size(); i++)
        {
            // 以s[i]为中心的最长回文串
            string s1 = palindrome(s, i, i);

            // 以s[i]和s[i+1]为中心的最长回文串
            string s2 = palindrome(s, i, i+1);

            ret = ret.size() > s1.size() ? ret : s1;
            ret = ret.size() > s2.size() ? ret : s2;
        }

        return ret;
    }

    string palindrome(string s, int l, int r)
    {
        // 防止越界
        while(l >= 0 && r < s.size() && s[l] == s[r])
        {
            // 向两边展开
            l--;
            r++;
        }

        // 返回以s[l]和s[r]为中心的最长回文串
        return s.substr(l + 1, r - l - 1);
    }
};


// 最长回文子串
class Solution {
public:
    string longestPalindrome(string s) 
    {
        string ret = "";

        for(int i = 0; i < s.size(); i++)
        {
            // 以s[i]为中心的最长回文串
            string s1 = palindrome(s, i, i);

            // 以s[i]和s[i+1]为中心的最长回文串
            string s2 = palindrome(s, i, i+1);

            ret = ret.size() > s1.size() ? ret : s1;
            ret = ret.size() > s2.size() ? ret : s2;
        }

        return ret;
    }

    string palindrome(string s, int l, int r)
    {
        // 防止越界
        while(l >= 0 && r < s.size() && s[l] == s[r])
        {
            // 向两边展开
            l--;
            r++;
        }

        return s.substr(l + 1, r - l - 1);
    }
};


// 两数之和 - 输入有序数组
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];
            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                return {left+1, right+1};
            }
        }

        return {-1, -1};
    }
};


// 删除有序数组中的重复项
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast遇到不重复的值就赋给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != nums[slow])
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        return slow+1;
    }
};


// 移除元素
class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast遇到值不为val的元素就赋值给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


// 移除零
class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 先按照 移除元素 思路，将0全部移除
        int p = removeElement(nums, 0);

        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }

            fast++;
        }

        return slow;
    }
};


// 反转字符串
class Solution {
public:
    void reverseString(vector<char>& s) 
    {
        int left = 0, right = s.size() - 1;

        while(left < right)
        {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
};


// 最长回文子串
class Solution {
public:
    string longestPalindrome(string s) 
    {
        string ret = "";

        for(int i = 0; i < s.size(); i++)
        {
            // 以s[i]为中心的最长回文子串
            string s1 = palindrome(s, i, i);

            // 以s[i]和s[i+1]为中心的最长回文子串
            string s2 = palindrome(s, i, i+1);

            ret = ret.size() > s1.size() ? ret : s1;

            ret = ret.size() > s2.size() ? ret : s2;
        }

        return ret;
    }

    string palindrome(string s, int l, int r)
    {
        // 防止越界
        while(l >= 0 && r < s.size() && s[l] == s[r])
        {
            l--;
            r++;
        }

        return s.substr(l + 1, r - l - 1);
    }
};


// 删除排序链表中的重复元素
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        // 断开与后面重复元素的连接
        slow->next = nullptr;

        return head;
    }
};



// 剑指offer - 和为s的两个数字
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left < right)
        {
            int sum = nums[left] + nums[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                return {nums[left], nums[right]};
            }
        }

        return {-1, -1};
    }
};


// 剑指offer - 排序数组中的两个数字之和
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                return {left, right};
            }
        }

        return {-1, -1};
    }
};


// 剑指offer - 最长不含重复字符的子字符串
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char, int> window;

        int left = 0, right = 0;

        int res = 0;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            window[c]++;

            while(window[c] > 1)
            {
                char d = s[left];

                left++;

                window[d]--;
            }

            res = max(res, right - left);
        }

        return res;
    }
};


// 剑指offer - 字符串中的变位词
class Solution {
public:
    bool checkInclusion(string s1, string s2) 
    {
        unordered_map<char, int> window, need;
        for(char c : s1) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        while(right < s2.size())
        {
            char c = s2[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                {
                    valid++;
                }
            }

            while(right - left >= s1.size())
            {
                if(valid == need.size())
                    return true;

                char d = s2[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return false;
    }
};


// 剑指offer - 字符串中的所有变位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
        unordered_map<char, int> window, need;
        for(char c : p) need[c]++;

        int left = 0, right = 0;
        int valid = 0;
        vector<int> res;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(right - left >= p.size())
            {
                if(valid == need.size())
                {
                    res.push_back(left);
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return res;
    }
};


// 剑指offer - 含有所有字符的最短字符串
class Solution {
public:
    string minWindow(string s, string t) 
    {
        unordered_map<char, int> window, need;
        for(char c : t) need[c]++;

        int left = 0, right = 0;

        int valid = 0;

        int start = 0, len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];

            right++;

            if(need.count(c))
            {
                window[c]++;

                if(window[c] == need[c])
                    valid++;
            }

            while(valid == need.size())
            {
                if(right - left < len)
                {
                    start = left;
                    len = right - left;
                }

                char d = s[left];

                left++;

                if(need.count(d))
                {
                    if(window[d] == need[d])
                        valid--;

                    window[d]--;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};


// 剑指offer - 排序数组中两个数字之和
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;
        
        while(left < right)
        {
            int sum = numbers[left] + numbers[right];

            if(sum < target)
                left++;
            else if(sum > target)
                right--;
            else if(sum == target)
                return {left, right};
        }

        return {};
    }
};



// 剑指offer - 和为s的两个数字
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left < right)
        {
            int sum = nums[left] + nums[right];

            if(sum < target)
                left++;
            else if(sum > target)
                right--;
            else
                return {nums[left], nums[right]};
        }

        return {};
    }
};



class Solution {
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        // 先将二维数组沿着对角线反转，再反转每一行
        int n = matrix.size();

        for(int i = 0; i < n; i++)
        {
            for(int j = i; j < n; j++)
            {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        for(auto& row : matrix)
        {
            reverseRow(row);
        }
    }

    void reverseRow(vector<int>& row)
    {
        int n = row.size();

        int i = 0, j = n - 1;

        while(i < j)
        {
            int temp = row[i];
            row[i] = row[j];
            row[j] = temp;
            i++;
            j--;
        }
    }
};


class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(),  n = matrix[0].size();

        int upperBorder = 0, lowerBorder = m - 1;
        int leftBorder = 0, rightBorder = n - 1;

        vector<int> res;

        // res.size() == m * n就停止了
        while(res.size() < m * n)
        {
            if(upperBorder <= lowerBorder)
            {
                // 上边界：从左到右
                for(int i = leftBorder; i <= rightBorder; i++)
                {
                    res.push_back(matrix[upperBorder][i]);
                }
                // 上边界上移
                upperBorder++;
            }

            if(leftBorder <= rightBorder)
            {
                // 右边界：从上到下
                for(int i = upperBorder; i <= lowerBorder; i++)
                {
                    res.push_back(matrix[i][rightBorder]);
                }

                // 右边界左移
                rightBorder--;
            }

            if(upperBorder <= lowerBorder)
            {
                // 下边界；从右到左
                for(int i = rightBorder; i >= leftBorder; i--)
                {
                    res.push_back(matrix[lowerBorder][i]);
                }

                // 下边界上移
                lowerBorder--;
            }

            if(leftBorder <= rightBorder)
            {
                // 左边界：从下到上
                for(int i = lowerBorder; i >= upperBorder; i--)
                {
                    res.push_back(matrix[i][leftBorder]);
                }

                // 左边界右移
                leftBorder++;
            }
        }

        return res;
    }
};


class Solution {
public:
    vector<vector<int>> generateMatrix(int n) 
    {
        vector<vector<int>> matrix(n, vector<int>(n, 0));

        int upperBoder = 0, lowerBoder = n - 1;
        int leftBoder = 0, rightBoder = n - 1;

        int num = 1;

        while(num <= n * n)
        {
            // 上边界：从左向右遍历
            if(upperBoder <= lowerBoder)
            {
                for(int i = leftBoder; i <= rightBoder; i++)
                    matrix[upperBoder][i] = num++; // 后置++
                
                // 上边界下移
                upperBoder++;
            }

            // 右边界：从上到下遍历
            if(leftBoder <= rightBoder)
            {
                for(int i = upperBoder; i <= lowerBoder; i++)
                    matrix[i][rightBoder] = num++;

                rightBoder--;
            }

            // 下边界：从右向左遍历
            if(upperBoder <= lowerBoder)
            {
                for(int i = rightBoder; i >= leftBoder; i--)
                    matrix[lowerBoder][i] = num++;

                lowerBoder--;
            }

            // 左边界：从下向上遍历
            if(leftBoder <= rightBoder)
            {
                for(int i = lowerBoder; i >= upperBoder; i--)
                    matrix[i][leftBoder] = num++;

                leftBoder++;
            }
        }

        return matrix;
    }
};


class NumArray {
public:

    // 定义前缀和数组
    vector<int> preSum;

    NumArray(vector<int>& nums) 
    {
        int n = nums.size();

        preSum.resize(n + 1);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
    }
    
    int sumRange(int left, int right) 
    {
        return preSum[right + 1] - preSum[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */


class NumMatrix {
public:

    // 定义二维前缀和数组
    vector<vector<int>> preSum;

    NumMatrix(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();

        preSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i-1][j-1] - preSum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) 
    {
        return preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */


class NumMatrix {
public:

    vector<vector<int>> preSum; // 二维前缀和数组

    NumMatrix(vector<vector<int>>& matrix) 
    {
        int m = matrix.size(), n = matrix[0].size();

        preSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) 
    {
        return preSum[row2+1][col2+1]-preSum[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */


class NumMatrix
{
    vector<vector<int>> preSum;

public:
    NumMatrix(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();

        preSum = vector<vector<int>>(m+1, vector<int>(n+1, 0));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];
            }
        }
    }

    int sum(int row1, int col1, int row2, int col2)
    {
        return preSum[row2+1][col2+1]-preSum[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];
    }
};


class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m = mat.size(), n = mat[0].size();

        vector<vector<int>> res(m, vector<int>(n, 0));

        NumMatrix numMatrix(mat);

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                // 左上角的坐标
                int x1 = max(i - k, 0);
                int y1 = max(j - k, 0);

                // 右下角的坐标
                int x2 = min(i + k, m - 1);
                int y2 = min(j + k, n - 1);

                res[i][j] = numMatrix.sum(x1, y1, x2, y2);
            }
        }

        return res;
    }
};


class Solution {
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();

        vector<int> preSum(n+1, 0);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i-1]+nums[i-1];
        }

        for(int i = 1; i < preSum.size(); i++)
        {
            // 计算nums[i-1]左右两边之和是否相同
            int leftSum = preSum[i-1] - preSum[0];
            int rightSum = preSum[n] - preSum[i];

            if(leftSum == rightSum)
                return i - 1;
        }

        return -1;
    }
};


class Solution {
public:
    int findMaxLength(vector<int>& nums) 
    {
        int n = nums.size();

        vector<int> preSum(n + 1, 0);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
        }

        // 建立前缀和到索引的映射
        unordered_map<int, int> valToIndex;
        int res = 0;

        for(int i = 0; i < preSum.size(); i++)
        {
            if(valToIndex.find(preSum[i]) == valToIndex.end())
                valToIndex[preSum[i]] = i;
            else
                res = max(res, i - valToIndex[preSum[i]]);
        }

        return res;
    }
};


class Solution {
public:
    int findMaxLength(vector<int>& nums) 
    {
        int n = nums.size();
        // 建立前缀和数组
        vector<int> preSum(n + 1, 0);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i-1] + (nums[i-1] == 0 ? -1 : 1);
        }

        // 建立前缀和数组到索引的映射
        unordered_map<int, int> valToIndex;
        int res = 0;
        for(int i = 0; i < preSum.size(); i++)
        {
            if(valToIndex.find(preSum[i]) == valToIndex.end())
                valToIndex[preSum[i]] = i;
            else
                res = max(res, i - valToIndex[preSum[i]]);
        }

        return res;
    }
};


class NumMatrix {
public:

    vector<vector<int>> preSum;

    NumMatrix(vector<vector<int>>& matrix) 
    {
        // 构造二维前缀和数组
        int m = matrix.size(), n = matrix[0].size();

        preSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                preSum[i][j] = preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) 
    {   
        return preSum[row2+1][col2+1]-preSum[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */


class NumMatrix
{
public:
    // 构造一个二维前缀和
    vector<vector<int>> preSum;

    NumMatrix(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();

        preSum = vector<vector<int>>(m+1, vector<int>(n+1, 0));

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                preSum[i][j] = preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];
            }
        }
    }

    int Sum(int row1, int col1, int row2, int col2)
    {
        return preSum[row2+1][col2+1]-preSum[row2+1][col1]-preSum[row1][col2+1]+preSum[row1][col1];
    }
};


class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m = mat.size(), n = mat[0].size();

        NumMatrix numMatrix(mat);

        vector<vector<int>> res(m, vector<int>(n, 0));

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int x1 = max(i-k, 0);
                int y1 = max(j-k, 0);
                int x2 = min(i+k, m-1);
                int y2 = min(j+k, n-1);

                res[i][j] = numMatrix.Sum(x1, y1, x2, y2);
            }
        }

        return res;
    }
};


class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k)
    {
        int n = nums.size();
        // 构建一维前缀和数组
        vector<int> preSum(n + 1, 0);

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i-1] + nums[i-1];
        }

        // 建立前缀和与k的余数和索引的映射
        unordered_map<int, int> valToIndex;
        for(int i = 0; i < preSum.size(); i++)
        {
            // 如果前缀和与k的余数和索引的映射不存在，则加入其中
            if(valToIndex.find(preSum[i] % k) == valToIndex.end())
                valToIndex[preSum[i] % k] = i;

            // 如果已经存在，则什么都不做
        }

        for(int i = 0; i < preSum.size(); i++)
        {
            int need = preSum[i] % k;

            if(valToIndex.count(need))
            {
                if(i - valToIndex[need] >= 2)
                    return true;
            }
        }

        return false;
    }
};


class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        int n = nums.size();

        vector<int> preSum(n + 1, 0);

        // 建立前缀和和到前缀和出现次数的映射
        unordered_map<int, int> count;

        count[0] = 1;

        int res = 0;

        for(int i = 1; i < preSum.size(); i++)
        {
            preSum[i] = preSum[i-1] + nums[i-1];

            // 如果存在值为need的前缀和
            // 说明存在以nums[i-1]结尾符合题意的子数组
            int need = preSum[i] - k;

            if(count.count(need))
                res += count[need];

            if(!count.count(preSum[i]))
                count[preSum[i]] = 1;
            else
                count[preSum[i]]++;
        }

        return res;
    }
};


class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) 
    {
        // 思路：先算出被覆盖区间的个数，然后数组大小减去它即可
        // 先按照起点升序排序，起点相同再按照终点降序排序
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b)
        {
            if(a[0] == b[0])
                return a[1] > b[1];

            return a[0] < b[0];
        });

        // 计算新合并后的区间
        int left = intervals[0][0];
        int right = intervals[0][1];

        int res = 0; // 计算结果
        for(int i = 1; i < intervals.size(); i++)
        {
            vector<int> inv = intervals[i];

            // 一共有三种情况
            // 一是覆盖，二是相交，三是完全不相交
            if(left <= inv[0] && right >= inv[1])
                res++;

            if(right >= inv[0] && right <= inv[1])
                right = inv[1];

            if(right <= inv[0] && right <= inv[1])
            {
                left = inv[0];
                right = inv[1];
            }
        }

        return intervals.size() - res;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        // 按照起点升序排列
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b)
        {
            return a[0] < b[0];
        });

        vector<vector<int>> res; //记录结果
        res.push_back(intervals[0]);

        for(int i = 1; i < intervals.size(); i++)
        {
            // 数组last是结果数组第一行元素的引用
            vector<int>& last = res.back();
            vector<int> cur = intervals[i];

            if(cur[0] <= last[1])
            {
                last[1] = max(cur[1], last[1]);
            }
            else
            {
                res.push_back(cur);
            }
        }

        return res;
    }
};


class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        // 按照起点升序
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b)
        {
            return a[0] < b[0];
        });

        vector<vector<int>> res;

        res.push_back(intervals[0]);

        for(int i = 1; i < intervals.size(); i++)
        {
            vector<int>& last = res.back(); // last是结果数组的第一行的引用

            vector<int> cur = intervals[i];

            if(cur[0] <= last[1])
            {
                last[1] = max(cur[1], last[1]);
            }
            else
            {
                res.push_back(cur);
            }
        }

        return res;
    }
};


class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];
            
            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else
            {
                return {left+1, right+1};
            }
        }

        return {-1, -1};
    }
};


class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针
        // fast走在前面探路，遇到不重复的值就赋给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }

        return slow + 1;
    }
};


class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针
        // fast走在前面探路，遇到值不为val的元素就赋给slow
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 先按照移除元素思路，将0全部移除
        int p = moveElement(nums, 0);

        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    int moveElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};


class Solution {
public:
    void reverseString(vector<char>& s) 
    {
        int left = 0, right = s.size() - 1;

        while(left < right)
        {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
};


class Solution {
public:
    string longestPalindrome(string s) 
    {
        string ret = "";

        for(int i = 0; i < s.size(); i++)
        {
            // 以s[i]为中心的最长回文子串
            string ret1 = isPalindrome(s, i, i);

            // 以s[i]和s[i+1]为中心的最长回文子串
            string ret2 = isPalindrome(s, i, i+1);

            ret = ret.size() > ret1.size() ? ret : ret1;
            ret = ret.size() > ret2.size() ? ret : ret2;
        }

        return ret;
    }

    string isPalindrome(string s, int l, int r)
    {
        while(l >= 0 && r < s.size() && s[l] == s[r])
        {
            l--;
            r++;
        }

        return s.substr(l + 1, r - l - 1);
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }

        slow->next = nullptr;

        return head;
    }
};


class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        int left = 0, right = nums.size() - 1;

        while(left < right)
        {
            int sum = nums[left] + nums[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else
            {
                return {nums[left], nums[right]};
            }
        }

        return {-1, -1};
    }
};


class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            int sum = numbers[left] + numbers[right];

            if(sum < target)
            {
                left++;
            }
            else if(sum > target)
            {
                right--;
            }
            else
            {
                return {left, right};
            }
        }

        return {-1, -1};
    }
};


class Solution {
public:
    vector<int> exchange(vector<int>& nums) 
    {
        // 定义快慢指针
        // fast在前面探路，遇到奇数就和slow交换
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] % 2 == 1)
            {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++; 
            }
            fast++;
        }

        return nums;
    }
};


class Solution {
public:
    bool isPalindrome(string s) 
    {
        // 将所有字母和数字转换成小写，并过滤掉空格和标点
        string res = "";

        for(int i = 0; i < s.size(); i++)
        {
            char c = s[i];

            if(isalnum(c)) // 判断是否是字母和数字
            {
                res += tolower(c); // 将其转换成小写字母
            }
        }

        s = res;

        int left = 0, right = s.size() - 1;

        while(left < right)
        {
            if(s[left] != s[right])
                return false;
            
            left++;
            right--;
        }

        return true;
    }
};



